package 笔试.拼多多;

import java.util.Scanner;

/**
 * 对于给定参数A、B和C，数字Q是否属于该集合
 *
 * 思路：判断能否写成（C^n）*A+m*B的形式
 *
 * 2
 * 1 2 3 4
 * 2 3 4 6
 * 0
 * 0
 */
public class PinDuoDuoDemo03 {
    /*public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] res = new int[n];
        for(int j=0;j<n;j++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            int q = sc.nextInt();
            boolean[] dp = new boolean[q + 1];
            dp[0] = true;
            if (q > a) dp[a] = true;
            for (int i = 1; i <= q; i++) {
                if (i > b) {
                    if (i % c == 0) dp[i] = dp[i - b] || dp[i / c];
                    else dp[i] = dp[i - b];
                }
            }
            if (dp[q]) res[j] = 1;
            else res[j] = 0;
        }
        for(int i=0;i<n;i++){
            System.out.println(res[i]);
        }

    }*/

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] res = new int[n];
        for(int j=0;j<n;j++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            int q = sc.nextInt();
            if(c==1){
                if(((q-a)%b)==0){
                    System.out.println(1);
                }else{
                    System.out.println(0);
                }
            }else{
                int tempC=1;
                while (tempC*a<=q){
                    if((q-tempC*a)%b==0){
                        System.out.println(1);
                    }
                    tempC = tempC*c;
                }
                System.out.println(0);
            }

        }
    }





}
